package com.sjb.training.lc;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * lc.977 有序数组的平方
 * @Author: 有点儿意思
 * @Description:
 */
public class SortedSquares {

    public static void main(String[] args) {
        int[]  nums = {7,-3,2,3,11};
        int[] sortedSquares = sortedSquares(nums);
        Arrays.sort(sortedSquares);
        System.out.println(Arrays.toString(sortedSquares));
    }

    public static int[] sortedSquares(int[] nums) {
        int[] squaresNums = new int[nums.length];
        int i = 0;
        for (; i < nums.length; i++) {
            squaresNums[i] = nums[i] * nums[i];
        }
        return squaresNums;
    }

    static void quickSorted (int[] nums ,int l,int r){
        if(l >= r){
            return;
        }
        int i = partition(nums,l,r);
        quickSorted(nums,l,i-1);
        quickSorted(nums,i+1,r);
    }

    static int partition(int[] nums,int l ,int r){
        int ra = (int)(1 + Math.random() * (r - 1 + 1));
        swap(nums,l,ra);
        int i = l, j = r;
        while (i < j){
            while (i < j && nums[j] >= nums[l]){
                j--;
            }
            while (i < j && nums[i] <= nums[l]){
                i++;
            }
            swap(nums, i,l);
        }
        return i;
    }

    static void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
